package com.example.demo.hot100;

/**
 * @Classname no5
 * @Description
 * @Date 2023/12/19 15:07
 * @Created by jyl
 *
 * 合并两个有序链表
 * 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接两个链表的所有节点组成的。
 */
public class no5 {

    public static void main(String[] args) {
        // 创建两个有序链表
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        // 创建 MergeTwoSortedLists 实例
        MergeTwoSortedLists merger = new MergeTwoSortedLists();

        // 调用 mergeTwoLists 函数进行合并
        ListNode result = merger.mergeTwoLists(l1, l2);

        // 输出合并后的链表
        printList(result);
    }

    // 辅助方法：打印链表
    private static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public static class MergeTwoSortedLists {

        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            // 递归终止条件：其中一个链表为空
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }

            // 比较两个链表的头节点值，选择较小的节点作为当前节点
            if (l1.val < l2.val) {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            } else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }
}
